Routing an integrated circuit involves determining the placement of wires to electrically connect integrated circuit devices and cells so that the integrated circuit operates correctly. For small integrated circuits, routing can be performed by a circuit designer who manually adds new wires to make the necessary connections in the integrated circuit. Often, the designer repositions devices and cells to make room for the new wires. Although manual routing can provide relatively compact designs, the manual approach is impractical for large integrated circuits containing millions of transistors.
For large integrated circuits, routing is performed automatically by a routing mechanism known as a “router” that is typically implemented as a software tool on a computer-aided design system. A router receives a data representation of the integrated circuit (a “layout”) and the electrical connections to be made between devices and cells contained in the integrated circuit layout (a “netlist”). The router determines where to place new wires in the integrated circuit layout to make the specified connections. The placement of the new wires is important since the length and placement of the new wires can have a direct effect on the performance of the integrated circuit. After the router has determined where to place the new wires, the router updates the integrated circuit layout to reflect the new wires.
Routing is typically performed in two phases: global routing and detailed routing. Global routing generally involves determining the general placement of the new wires. Conventionally, a spanning tree is created to determine which pairs of points will be connected. One particular type of spanning tree is a Steiner tree, which allows for new points, referred to as Steiner points, that were not in the original list of connection points. The new points provide additional flexibility in connecting the pairs of points and can reduce the total wire length by 10 to 15%, thereby reducing signal transmission time.
During the detailed routing phase, the router implements the connection between each pair of points by adding the new wires. Ideally, all of the new wires would be implemented as straight lines between the specified connection points. However, the new wires usually have to be bent to avoid obstacles, i.e., devices and cells, in the layout. In addition, the angle between a given pair of points will not normally be an angle supported by the router (e.g., a multiple of ninety degrees for most current routers) and so at least one bend will be necessary to ensure that all components of the wire have a reasonable direction. Thus, various routing approaches are used to optimize the placement of the new wires. Two of these approaches include the channel routing approach and the area routing approach.
The channel routing approach generally involves converting the two-dimensional area routing problem into a series of one-dimensional channel routing problems. For a description of the channel routing approach, see Introduction to CAD for VLSI, First Edition (1987), by Stephen M. Trimberger, Kluwer Academic Publishers, Boston, ISBN 0-89838-231-9.
In the channel routing approach, the router chooses the channels in which the new wires travel horizontally and the slots in which the new wires travel vertically between channels. Many of these choices are based upon the placement of the standard cells in the rows. The channel router then optimizes the usage of horizontal routing tracks in an attempt to minimize the height of the channel. Even this is NP-hard, so most channel routers impose a constraint that each net in the channel have a single horizontal spine in a single routing track. Under this constraint, each track is assigned to a different net at each slot location using a graph coloring algorithm. Horizontal wires are routed in one layer and vertical wires are routed in a second layer. If more layers are available, the layers typically alternate directions. Most commercial routers use some form of channel router to perform detailed routing and then compact the channel to simulate having multiple spines per net. FIG. 1A is a block diagram of a portion of an integrated circuit layout 100 that requires a channel with three routing tracks. FIG. 1B is a block diagram of a portion of an integrated circuit layout 150 that requires a channel with four routing tracks. The channel has been compacted so that it uses space equivalent to three routing tracks.
The primary benefit of the channel routing approach is simplicity, albeit at the expense of size and flexibility. However, the channel routing approach is not without its disadvantages. Specifically, the channel routing approach becomes impractical or impossible if there are significant numbers of obstacles extending into the channel, or if pins and/or obstacles are in the middle of the routing area, or if there are pin connections on all four sides of the region to be routed (which greatly increases the difficulty of assigning tracks for spines).
The classic area router is the Lee Router, also known as a Maze Router, which routes one wire at a time by progressively searching all grid locations between the pair of points being routed. If there is a way to connect the points, the Lee Router will find the most efficient way, but the number of locations to be searched is very large (especially if more than one routing layer can be used). As a result, area routers are generally more powerful than their channel router counterparts, but they tend to require substantially more computational resources to operate and are more difficult to implement. For large integrated circuits, area routers can be impractical. See “Chip Level Area Routing,” Le-Chin Eugene Liu et al., Proceedings of the 1998 International Symposium on Logic Design, pp. 197-204. Note that the authors split the die into smaller regions for area routing.
FIG. 2 is a block diagram 200 that illustrates how a “wave front” type search is used to establish a path 202 from a source pin 204 to a destination pin 206 around an obstacle 208. For each point on the wave front, defined by an x-axis 210 and a y-axis 212, four adjacent grid locations must be tested to see if they have been traversed, are obstacles, or have been used in a different wire. Line 214 represents the locus of points eighteen units from source pin 204. Every untraversed, unused, non-obstacle location must then be added to the next wave front. Choosing a smaller grid will result in many more locations to be examined, so the router typically works on a grid that is the size of the contact routing pitch.
FIGS. 3A and 3B are block diagrams 300 and 350, respectively, that illustrate the wasted space induced by the use of a routing grid in a router, such as an area router or a channel router. Wires without contacts typically require 10 to 20% less space. As a result, a routing grid based upon wires having contacts can waste a significant amount of space. In FIG. 3A, wires 302 and 304, each 0.5 lambda wide (the particular units are immaterial), have a pitch of 1.25 lambda, because of the minimum required spacing of 0.5 lambda between contact 306 and contact 308. In contrast, the wires 352 and 354 of FIG. 3B have a pitch of 1.0 lambda, since wires 352 and 354 do not have contacts.
It is important to note that if a Lee Router is implemented with multiple routing layers, then each point in the wave front has even more possibilities: left, right, up, down, go to the next routing layer if any, or go to the previous routing layer if any. Any sequential router such as the Lee Router must also concern itself with interference between the individual wires. Completing one wire may well block another. Because an optimal routing order is generally not known in advance, area routers typically must implement some form of rip-up and reroute, in which some number of existing wires are removed, another wire drawn, and the ripped-up wires redrawn. This may lead to still more blockages, requiring further rerouting. In the worst case the area router might not be able to find a feasible solution for all wires.
Many enhancements have been suggested to the basic Lee Router. See, for example, Combinatorial Algorithms for Integrated Circuit Layout, by Thomas Lengauer, John Wiley & Sons Ltd., England, ISBN 0-471-92838-0). It is noteworthy that these enhancements are restricted to orthogonal routing and mostly require the use of a coarse routing grid.
Commercial integrated circuit routing tools sometimes use a channel routing mechanism first and then an area routing mechanism to complete unroutes or to implement small changes in the circuit after it has been built once already (i.e. Engineering Change Orders or ECOs), when it is advantageous to minimize the number of production mask levels that must be changed. Unroutes are typically short sections of connecting wires that could not be completed with a channel router due to underestimation of resource requirements. In these situations, adding a track in a channel would force all transistor rows to be moved apart, requiring that all mask levels be rebuilt.
A significant limitation with conventional routing approaches, including both the channel routing approach and the area routing approach, is the inability to modify the geometry around a wire being defined. There are several reasons for this limitation. One reason is that many conventional routers are strictly inter-cell routers that connect predefined cells only. Another reason is that most conventional routing approaches use only orthogonal geometry for wires and geometry changes such as clipping the corner of an enclosure do not provide a benefit unless the wire passing it is non-orthogonal. A third reason is that non-orthogonal wires do not efficiently fit onto a coarse routing grid, requiring either a wasteful grid size or a “gridless” router. Although some gridless routers have been designed, none of them are capable of routing non-orthogonal wires. Non-orthogonal routing can reduce overall wire length by up to 7% compared to orthogonal routing, resulting in both area savings and delay reductions.
Therefore, based on the need to route connections in integrated circuits and the limitations in the prior approaches, an approach for automatically routing an integrated circuit that does not suffer from limitations inherent in conventional routing approaches is highly desirable.